package sf.sort;

/**
 * 插入排序
 */
public class InsertSort implements Sort{

    public void sort(int[] unsorted) {
        // 插入排序就是对于已排序好的数组，插入新的数，寻找插入的位置
        for (int i = 1; i < unsorted.length; i++) {
            // 第一个数肯定排序好了，所以从1开始
            int k = unsorted[i];
            // 在前面排好序中寻找
            // 从后面找起
            int j = i-1;
            for (;j >= 0; j--) {
                if (unsorted[j] <= k) {
                    break;
                } else {
                    unsorted[j + 1] = unsorted[j];
                }
            }
            unsorted[j+1] = k;
        }
    }

    public static void main(String[] args) {

    }

}
